#include <bits/stdc++.h>
using namespace std;
struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    string solve(string s, string t)
    {
        int nums1ind = s.size() - 1;
        int nums2ind = t.size() - 1;
        int count = 0;
        string ret;
        for (; nums1ind >= 0 || nums2ind >= 0; nums1ind--, nums2ind--)
        {
            int num1 = nums1ind >= 0 ? s[nums1ind] - '0' : 0;
            int num2 = nums2ind >= 0 ? t[nums2ind] - '0' : 0;
            count += num1 + num2;
            ret.push_back(count % 10 + '0');
            count /= 10;
        }
        while (count)
        {
            ret.push_back(count + '0');
            count /= 10;
        }
        while (ret.size() > 1 && ret[ret.size() - 1] == '0')
            ret.pop_back();
        reverse(ret.begin(), ret.end());
        return ret;
    }
    ListNode *addInList(ListNode *head1, ListNode *head2)
    {
        string num1, num2;
        ListNode *cur = head1;
        while (cur)
        {
            num1.push_back(cur->val + '0');
            cur = cur->next;
        }
        cur = head2;
        while (cur)
        {
            num2.push_back(cur->val + '0');
            cur = cur->next;
        }

        string ret = solve(num1, num2);
        cout << num1 << " " << num2 << " " << ret << endl;
        ListNode *newhead = nullptr;
        ListNode *prev = nullptr;
        for (int i = 0; i < ret.size(); i++)
        {
            if (i == 0)
            {
                newhead = new ListNode(ret[i] - '0');
                prev = newhead;
            }
            else
            {
                ListNode *node = new ListNode(ret[i] - '0');
                prev->next = node;
                prev = node;
            }
        }
        return newhead;
    }
};

// 直接在链表中进行操作

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution1
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */

    ListNode *reverseList1(ListNode *head)
    {
        ListNode *cur = head;
        ListNode *prev = nullptr;
        while (cur)
        {
            ListNode *next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    ListNode *reverseList2(ListNode *head)
    {
        // 如果空返回空 如果是一个节点了就直接返回本身 就是反转后的头节点
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *newhead = reverseList2(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newhead;
    }
    ListNode *addInList(ListNode *head1, ListNode *head2)
    {
        ListNode *l1 = reverseList1(head1);
        ListNode *l2 = reverseList1(head2);
        ListNode *newhead=new ListNode(0);
        ListNode*prevnode=newhead;
        int count=0;
        while(l1||l2||count)
        {
            int num1=l1==nullptr?0:l1->val;
            int num2=l2==nullptr?0:l2->val;
            count+=num1+num2;
            ListNode *node=new ListNode(count%10);
            prevnode->next=node;
            prevnode=node;
            count/=10;
            if(l1)
            l1=l1->next;
            if(l2)
            l2=l2->next;
        }
        ListNode*next=newhead->next;
        delete newhead;
        newhead=next;
        return reverseList1(newhead);
    }
};